"""
题目：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    示例 1：
    输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]
    
思路：计算链表长度。先计算链表长度size，则target= size - n + 1,在(1,target)之间循环，每次都将cur向后移一位，此时cur指向的是倒数第n-1个节点，此时令其下一个几点指向倒数第n+1个节点，
    此时令其下一个几点指向倒数第n个节点即可。
时间复杂度：O(L)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        size = 0
        cur = head
        while cur:
            size += 1
            cur = cur.next
        target = size - n + 1
        # if target < 0: return None
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy
        for i in range(1,target):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.next
